package Entity;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import Common.*;

public class ExpressionBuilder {
	ExpressionBuilder(){

	}

	//生成表达式组
		public List<Node> CreateExpressionTreeList(int n,int size){
			int num=0;
			List<Node> list = new ArrayList<Node>();
			for(int i=0;i<n;i++){
				Node node = CreateExpressionTree(size);
				boolean flag = false;
				for(Node no:list) {
					if(CheckTheSame(RealySortToComputable(no),RealySortToComputable(node))) {
						num++;
						i--;
						flag = true;
						break;
					}
				}
				if(!flag)
					list.add(node);
			}
			System.out.println("重复次数:   "+num);
			return list;
		}

	//表达式二叉树生成
	public Node CreateExpressionTree(int size) {
		Node root=new Node(CreateOperator());
		Random random = new Random();
		int operatorNum = random.nextInt(3);//运算符数量
		root = CreatNode(root,operatorNum,size);
		root.setHasBrackets(false);
		return root;
	}

	//查重
	public boolean CheckTheSame(Node node1,Node node2) {
		Node node11 = SortForCheck(SortForCheck(node1));
		Node node22 = SortForCheck(SortForCheck(node2));
		if(!node11.getValue().equals(node22.getValue())) {
			return false;
		}
		if(node11.getHasBrackets()!=node22.getHasBrackets()) {
			return false;
		}
		if(node11.getLeftChild()!=null&&node22.getLeftChild()!=null)
			if(!CheckTheSame(node11.getLeftChild(),node22.getLeftChild())){
				return false;
			}
		if(node11.getLeftChild()==null&&node22.getLeftChild()!=null)
			return false;
		if(node11.getLeftChild()!=null&&node22.getLeftChild()==null)
			return false;
		if(node11.getRightChild()!=null&&node22.getRightChild()!=null)
			if(!CheckTheSame(node11.getRightChild(),node22.getRightChild())){
				return false;
			}
		if(node11.getRightChild()==null&&node22.getRightChild()!=null)
			return false;
		if(node11.getRightChild()!=null&&node22.getRightChild()==null)
			return false;
		return true;
	}



	//查重时排序
	public Node SortForCheck(Node no) {
		Node node = new Node(no);
		if(isOperator(node.getValue())){
			if(node.getValue().equals("+")||node.getValue().equals("*")) {
				if(String1BiggerString2OrNot(SolveExpretionTree(node.getLeftChild()),SolveExpretionTree(node.getRightChild()))==-1){
					//大于
					Node l = SortForCheck(node.getLeftChild());
					Node r = SortForCheck(node.getRightChild());
					node.setLeftChild(r);
					node.setRightChild(l);
					return node;
				}
				if(String1BiggerString2OrNot(SolveExpretionTree(node.getLeftChild()),SolveExpretionTree(node.getLeftChild()))==0) {
					if(isOperator(node.getLeftChild().getValue())&&isOperator(node.getRightChild().getValue())) {
						//左右子树都是运算符
						if(ThisNodeOperatorValue(node.getLeftChild())==ThisNodeOperatorValue(node.getRightChild())) {
							Node l = SortForCheck(node.getLeftChild());
							Node r = SortForCheck(node.getRightChild());
							if(String1BiggerString2OrNot(SolveExpretionTree(l.getLeftChild()),SolveExpretionTree(r.getLeftChild()))==-1) {
								node.setLeftChild(r);
								node.setRightChild(l);
								return node;
							}
						}else if(ThisNodeOperatorValue(node.getLeftChild())<ThisNodeOperatorValue(node.getRightChild())) {
							Node l = SortForCheck(node.getLeftChild());
							Node r = SortForCheck(node.getRightChild());
							node.setLeftChild(r);
							node.setRightChild(l);
							return node;
						}
					}else if(isOperator(node.getRightChild().getValue())) {
						Node l = SortForCheck(node.getLeftChild());
						Node r = SortForCheck(node.getRightChild());
						node.setLeftChild(r);
						node.setRightChild(l);
						return node;
					}else {
						if(String1BiggerString2OrNot(SolveExpretionTree(node.getLeftChild()),SolveExpretionTree(node.getRightChild()))==-1) {
							Node l = SortForCheck(node.getLeftChild());
							Node r = SortForCheck(node.getRightChild());
							node.setLeftChild(r);
							node.setRightChild(l);
							return node;
						}
					}
				}else if(String1BiggerString2OrNot(SolveExpretionTree(node.getLeftChild()),SolveExpretionTree(node.getLeftChild()))==-1){
					Node l = SortForCheck(node.getLeftChild());
					Node r = SortForCheck(node.getRightChild());
					node.setLeftChild(r);
					node.setRightChild(l);
					return node;
				}
			}
			node.setLeftChild(SortForCheck(node.getLeftChild()));
			node.setRightChild(SortForCheck(node.getRightChild()));
			return node;
		}else {
			return node;
		}
	}


	//表达式二叉树生成核心函数
	public Node CreatNode(Node no,int n,int size) {
		Node node = new Node(no.getValue());
		node.setHasBrackets(no.getHasBrackets());
		Random random = new Random();
		int flag = random.nextInt(2);
		Node left;
		Node right;
		if(flag==0) {
			node.setHasBrackets(false);
		}
		else {
			node.setHasBrackets(true);
		}
		if(n!=0) {
			left = new Node(CreateOperator());
			left = CreatNode(left,n-1,size);
		}else {
			left = new Node(CreateNum(size));
		}
		right=new Node(CreateNum(size));
		int flag2 = random.nextInt(2);
		if(flag2==0) {
			node.setValue(CreateOperator());
			node.setLeftChild(left);
			node.setRightChild(right);
		}else {
			node.setLeftChild(right);
			node.setRightChild(left);
		}
		return node;
	}


	//算二叉树表达式
	public String SolveExpretionTree(Node no) {
		no = RealySortToComputable(no);
		if(isOperator(no.getValue())) {
			if(no.getValue().equals("+")) {
			//	System.out.println(SolveExpretionTree(no.getLeftChild())+no.getValue()+SolveExpretionTree(no.getRightChild()));
				return jiaFa(SolveExpretionTree(no.getLeftChild()),SolveExpretionTree(no.getRightChild()));
			}else if(no.getValue().equals("-")){
			//	System.out.println(SolveExpretionTree(no.getLeftChild())+no.getValue()+SolveExpretionTree(no.getRightChild()));
				return jianFa(SolveExpretionTree(no.getLeftChild()),SolveExpretionTree(no.getRightChild()));
			}else if(no.getValue().equals("*")) {
			//	System.out.println(SolveExpretionTree(no.getLeftChild())+no.getValue()+SolveExpretionTree(no.getRightChild()));
				return chengFa(SolveExpretionTree(no.getLeftChild()),SolveExpretionTree(no.getRightChild()));
			}else {
			//	System.out.println(SolveExpretionTree(no.getLeftChild())+no.getValue()+daoShu(SolveExpretionTree(no.getRightChild())));
				return chengFa(SolveExpretionTree(no.getLeftChild()),daoShu(SolveExpretionTree(no.getRightChild())));
			}
		}else {
			return no.getValue();
		}
	}
	public Node RealySortToComputable(Node no) {
		return SortToComputable(SortToComputable(no));
	}

	//假分数化简等
	public String FinalAnswer(Node Expretion) {
		String s = yueFen(SolveExpretionTree(Expretion));
		int[] a = decomposeFraction(s);
		if(a[0]<0) {
			if(-a[0]>a[1]) {
				int z = (-a[0])/a[1];
				int yu = (-a[0])%a[1];
				if(yu!=0)
					return "-"+z+"'"+yu+"/"+a[1];
				else
					return "-"+z;
			}else
				return s;
		}else if(a[0]==0) {
			return "0";
		}else {//a[0]>0
			if(a[0]>a[1]) {
				int z = a[0]/a[1];
				int yu = a[0]%a[1];
				if(yu!=0)
					return z+"'"+yu+"/"+a[1];
				else
					return z+"";
			}else
				return s;
		}
	}

	//二叉树排列成可直接计算二叉树
	public Node SortToComputable(Node no) {
		Node node= new Node(no);
		if(isOperator(node.getValue())) {//该节点是否操作符
			Node left = null;
			Node right = null;
			if(isOperator(node.getLeftChild().getValue())) {//左孩子节点是否为操作符
				//System.out.println("   左："+node.getLeftChild().getValue()+"   "+isOperator(node.getLeftChild().getValue()));
				//左孩子节点为操作符
				if(node.getLeftChild().getHasBrackets()) {//左孩子节点是否有括号
					//有括号,则将该节点作为另一个根节点去调用排列（递归调用）
					node.setLeftChild(SortToComputable(node.getLeftChild()));
				}else {//没括号,则比较操作符级别
					if(ThisNodeOperatorValue(node)>OperatorValue(node.getLeftChild())) {
						//若该节点操作符优先级大于左孩子节点的操作符,则进行变换后处理左孩子节点,顶点节点为left
//						System.out.println("   左："+ThisNodeOperatorValue(node)+">"+OperatorValue(node.getLeftChild()));
//						System.out.println("   左："+node.getValue()+">"+node.getLeftChild().getValue());
						left = new Node(node.getLeftChild());
						node.setLeftChild(SortToComputable(node.getLeftChild().getRightChild()));
						boolean s = left.getHasBrackets();
						left.setHasBrackets(node.getHasBrackets());
						node.setHasBrackets(s);
						left.setRightChild(new Node(node));
					}else {//若优先级小于等于，则直接处理左孩子节点，顶点节点不变
						node.setLeftChild(SortToComputable(node.getLeftChild()));
					}
				}
			}
			if(isOperator(node.getRightChild().getValue())) {//右孩子节点是否为操作符
				//System.out.println("   右："+node.getRightChild().getValue()+"   "+isOperator(node.getRightChild().getValue()));
				//右孩子节点为操作符
				if(node.getRightChild().getHasBrackets()) {//右孩子节点是否有括号
					//有括号,则将该节点作为另一个根节点去调用排列（递归调用）
					node.setRightChild(SortToComputable(node.getRightChild()));
				}else {//没括号,则比较操作符级别
					if(ThisNodeOperatorValue(node)>=OperatorValue(node.getRightChild())) {
//						System.out.println("   右："+ThisNodeOperatorValue(node)+">"+OperatorValue(node.getRightChild()));
//						System.out.println("   右："+node.getValue()+">"+node.getRightChild().getValue());
						//若该节点操作符优先级大于右孩子节点的操作符,则进行变换后处理左孩子节点
						right = new Node(node.getRightChild());
						boolean s = right.getHasBrackets();
						right.setHasBrackets(node.getHasBrackets());
						node.setHasBrackets(s);
						node.setRightChild(SortToComputable(node.getRightChild().getLeftChild()));
						right.setLeftChild(new Node(node));
					}else {//若优先级小于等于，则直接处理右孩子节点，顶点节点不变
						node.setRightChild(SortToComputable(node.getRightChild()));
					}
				}
			}
			if(left!=null&&right!=null) {//两边都有变化则left为顶点节点
				left.setRightChild(right);
				return left;
			}else if(left!=null) {//只有左节点变换则left为顶点节点
				return left;
			}else if(right!=null) {//只有右节点变换则right为顶点节点
				return right;
			}else {//若都没有变化则仍为node为顶点节点
				return node;
			}
		}else {//该节点为操作数，直接返回
			return node;
		}
	}



	//是否操作符
	public boolean isOperator(String s) {
		if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("➗")) {
			return true;
		}else {
			return false;
		}
	}

	public int OperatorValue(Node node) {
		String s = node.getValue().trim();
		if(node.getHasBrackets())return 3;//有括号的则当作操作数
		if(s.equals("+"))return 1;
		if(s.equals("-"))return 1;
		if(s.equals("*"))return 2;
		if(s.equals("➗"))return 2;
		return 3;//操作数优先级3
	}
	public int ThisNodeOperatorValue(Node node) {
		String s = node.getValue().trim();
		if(s.equals("+"))return 1;
		if(s.equals("-"))return 1;
		if(s.equals("*"))return 2;
		if(s.equals("➗"))return 2;
		return 3;//操作数优先级3
	}


	//生成运算符
	public String CreateOperator(){
		Random random = new Random();
		int t = random.nextInt(4);
		switch(t){
			case 0:return "+";
			case 1:return "-";
			case 2:return "*";
			default:return "/";
		}
	}

	//生成操作数
	public String CreateNum(int size) {
		Random random = new Random();
		int t = random.nextInt(3);
		if(t<=1){
			Integer a = random.nextInt(size)+1;
			return a.toString();
		}else{
			return CreateFraction(size);
		}
	}

	//创建一个分数
	public String CreateFraction(int size){
		Random random = new Random();
		int a = random.nextInt(size-1)+2;
		int b = random.nextInt(a-1)+1;
		int factor = CommonFactor(a,b);
		if(factor>1){
			a/=factor;
			b/=factor;
		}
		int c = random.nextInt(5);
		if(c<3){
			return b+"/"+a;
		}else{
			return (random.nextInt(size)+1)+"'"+b+"/"+a;
		}
	}

	//求公因数
	public  int CommonFactor(int a,int b){
        while(b != 0){
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

	//计算减法
		public String jianFa(String s1,String s2) {
			int[] a = decomposeFraction(s1);
			int[] b = decomposeFraction(s2);
			int[] c = new int[2];
			c[0]=a[0]*b[1]-b[0]*a[1];
			c[1]=a[1]*b[1];
			int d;
			if(c[0]<0) {
				d=CommonFactor(-c[0],c[1]);
			}else
				d= CommonFactor(c[0],c[1]);
			c[0]/=d;
			c[1]/=d;
			if(c[1]==1) {
				//System.out.println(c[0]+"");
				return c[0]+"";
			}else{
				//System.out.println(c[0]+"/"+c[1]);
				return c[0]+"/"+c[1];
			}
	 	}
	//计算加法
	public String jiaFa(String s1,String s2) {
		int[] a = decomposeFraction(s1);
		int[] b = decomposeFraction(s2);
		int[] c = new int[2];
		c[0]=a[0]*b[1]+b[0]*a[1];
		c[1]=a[1]*b[1];
		int d;
		if(c[0]<0) {
			d=CommonFactor(-c[0],c[1]);
		}else
			d= CommonFactor(c[0],c[1]);
		c[0]/=d;
		c[1]/=d;
		if(c[1]==1) {
			return c[0]+"";
		}else{
			return c[0]+"/"+c[1];
		}
 	}
	//计算乘法
	public String chengFa(String s1,String s2) {
		int[] a = decomposeFraction(s1);
		int[] b = decomposeFraction(s2);
		int[] c = new int[2];
		c[0]=a[0]*b[0];
		c[1]=a[1]*b[1];
		int d;
		if(c[0]<0) {
			d=CommonFactor(-c[0],c[1]);
		}else
			d= CommonFactor(c[0],c[1]);
		c[0]/=d;
		c[1]/=d;
		if(c[1]==1) {
			//System.out.println(c[0]+"");
			return c[0]+"";
		}else{
			//System.out.println(c[0]+"/"+c[1]);
			return c[0]+"/"+c[1];
		}
 	}
	//倒数
	public String daoShu(String s) {
		if(s.contains("/")) {
			int[] a = decomposeFraction(s);
			if(s.contains("-")) {
				return (-a[1])+"/"+(a[0]);
			}else
			return a[1]+"/"+a[0];
		}else {
			if(s.contains("-")) {
				return "-1/"+s.substring(1);
			}else
			return "1/"+s;
		}
	}
	//比较String的大小
	public int String1BiggerString2OrNot(String s1,String s2) {
		int[] a = decomposeFraction(s1);
		int[] b = decomposeFraction(s2);
		if(a[0]*b[1]>b[0]*a[1]) {
			return 1;
		}else if(a[0]*b[1]==b[0]*a[1]) {
			return 0;
		}else {
			return -1;
		}
	}
	//分解分数
	public int[] decomposeFraction(String s) {
		char[] fra = s.toCharArray();
		if(s.contains("'")) {
			int m = s.indexOf("'");
			int n = s.indexOf("/");
			String a="",b="",c="";
			for(int i=0;i<m;i++) {
				a+=fra[i];
			}
			for(int i=m+1;i<n;i++) {
				b+=fra[i];
			}
			for(int i=n+1;i<s.length();i++) {
				c+=fra[i];
			}
			int[] result = new int[2];
			int a1=Integer.parseInt(a),b1=Integer.parseInt(b),c1=Integer.parseInt(c);
			result[0]=a1*c1+b1;
			result[1]=c1;
			return result;
		}else if(s.contains("/")) {
			//System.out.println("需要转化的分数：  "+s);
			int n = s.indexOf("/");
			String a="",b="";
			if(s.contains("-")) {
				for(int i=1;i<n;i++) {
					a+=fra[i];
				}
			}else {
				for(int i=0;i<n;i++) {
					a+=fra[i];
				}
			}
			for(int i=n+1;i<s.length();i++) {
				b+=fra[i];
			}
			int[] result = new int[2];
			//System.out.println("要转换的数a：   "+a+"   要转换的数b：   "+b);
			int a1=Integer.parseInt(a),b1=Integer.parseInt(b);
			if(s.contains("-")) {
				result[0]=-a1;
			}else {
				result[0]=a1;
			}
			result[1]=b1;
			return result;
		}else {
			int[] result = new int[2];
			//System.out.println("要转换的数：   "+s);
			if(s.contains("-")) {
				result[0]=-Integer.parseInt(s.substring(1));
			}else{
				result[0]=Integer.parseInt(s);
			}
			result[1]=1;
			return result;
		}
	}
	//约分
	public String yueFen(String s) {
		int[] c = decomposeFraction(s);
		int d;
		if(c[0]<0) {
			d=CommonFactor(-c[0],c[1]);
		}else
			d= CommonFactor(c[0],c[1]);
		c[0]/=d;
		c[1]/=d;
		if(c[1]==1) {
			return c[0]+"";
		}else{
			return c[0]+"/"+c[1];
		}
	}


}
